import {BSTree,BSTNode} from './BSTree'
import assert from 'assert';

function getColor(node){
    if (node) return node.color;
    return 'b';
}

export class RBTNode extends  BSTNode{
    constructor(owner,value){
        super(owner,value);
    }

    insertFix(){
        let parent=this.parent;
        if (parent==this.owner) this.color='b';
        else if (parent.color=='b') this.color='r';
        else {
            let uncle = parent.sibling;
            let grand= parent.parent;
            if (uncle == null || uncle.color == 'b') {
                if (this===parent.left&&parent==grand.right||this===parent.right&&parent==grand.left){
                    parent=this.rotate();
                }
                parent.rotate();
                this.color='r';
                parent.color='b';
                grand.color='r';
            } else {
                this.parent.color='b';
                this.uncle.color='b';
                this.color='r';
                this.grandparent.insertFix();
            }
        }
    }

    assert() {
        super.assert();
        assert(this.color=='b'||this.color=='r');
        if (this.isRoot()) assert.equal(this.color, 'b');
        else if (this.color == 'r') {
            //console.log(this.value);
            assert(this.left == null || this.left.color == 'b');
            assert(this.right == null || this.right.color == 'b');
        }
        let l = this.left ? this.left.assert() : 1;
        let r = this.right ? this.right.assert() : 1;
        assert.equal(l, r);
        if (this.color == 'b') return l + 1;
        return l;
    }

    removeFix() {
        if (this.color != 'b') return;
        if (this.isRoot()) return;
        let sibling = this.sibling;
        if (getColor(sibling) == 'r') {
            this.parent.color = 'r';
            sibling.color = 'b';
            sibling.rotate();
            return this;
        } else {
            let parallel,cross;
            let parent=this.parent;
            if (this==parent.left) {
                parallel=sibling.left;
                cross=sibling.right;
            }else{
                parallel=sibling.right;
                cross=sibling.left;
            }
            if (getColor(cross)=='b'){
                if (getColor(parallel) == 'b'){
                    if (parent.color == 'b') {
                        sibling.color = 'r';
                        return parent;
                    } else {
                        parent.color = 'b';
                        sibling.color = 'r';
                    }
                }else {
                    parallel.color = 'b';
                    sibling.color = 'r';
                    parallel.rotate();
                    return this;
                }
            }else{
                sibling.color=parent.color;
                parent.color='b';
                cross.color='b';
                sibling.rotate();
            }
        }
    }

    replaceTree(node){
        for (let p=this;p!=null;p=p.removeFix());
        return super.replaceTree(node);
    }
}

export class RBTree extends BSTree{
    nodeType(){
        return RBTNode;
    }

    insert(value){
        let node=super.insert(value);
        node.insertFix();
    }

}